package org.myy.learn.hot.回溯;

import lombok.extern.slf4j.Slf4j;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

@Slf4j
public class 全排列 {
    public static List<List<Integer>> permute(int[] nums) {

        List<List<Integer>> result= new ArrayList<>();
        int len = nums.length;
        if (len == 0){
            return result;
        }

        Deque<Integer> path = new ArrayDeque<>();
        boolean[] used = new boolean[len];

        backTrack(nums, len, 0, path, used, result);
        return result;
    }

    private static void backTrack(int[] nums, int len, int depth, Deque<Integer> path, boolean[] used, List<List<Integer>> result) {
        if (depth == len){
            result.add(new ArrayList<>(path));
            return;   //ToDo 只结束当前层：回到上一层调用点的下一行代码
        }
        //ToDO 递归的流转步骤
        for (int i=0; i<len; i++){
            if (!used[i]){
                path.addLast(nums[i]);
                used[i] = true;

                backTrack(nums,len,depth+1, path, used, result);

                used[i] = false;
                path.removeLast();
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,2,3};
        List<List<Integer>> result = permute(nums);
        log.info("执行结束，全排列={}", result);
    }
}
